package crackingTheInterview;

public class BinarySearch {
	
	public static void main(String[] args){
		int[] array1= {1,2,3,4,5,6,7,8,9,10};
		int[] array2={2,3,6,8,10,12,15};
		int[] array3={2,5,5,8,9,9,20};
		
		System.out.println(search(array1,5));
		System.out.println(search(array1,1));
		System.out.println(search(array1,10));
		System.out.println(search(array1,8));
		
		System.out.println(search(array2,5));
		System.out.println(search(array2,2));
		System.out.println(search(array2,15));
		System.out.println(search(array2,10));
		
		System.out.println(search(array3,5));
		System.out.println(search(array3,9));
		System.out.println(search(array3,20));
		System.out.println(search(array3,10));
	}
	
	public static int search(int[] array, int key){
		int left = 0;
		int right = array.length;
		int middle = array.length/2;
		
		while(left<right){
			if(key==array[middle]){
				return middle;
			}
			else if(key<array[middle]){
				right = middle;
				middle =(right-left)/2+left;
			}
			else{//key>array[middle]
				left = middle+1;
				middle = (right-left)/2+left;
			}
		}
		return -1;
	}

}
